package com.leng.exercises;

import com.sun.xml.internal.bind.v2.TODO;

import java.util.Arrays;
import java.util.Random;

class Solution {

    /**
     * 1.两数之和
     * <p>
     * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
     * <p>
     * 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
     * 示例:
     * <p>
     * 给定 nums = [2, 7, 11, 15], target = 9
     * <p>
     * 因为 nums[0] + nums[1] = 2 + 7 = 9
     * 所以返回 [0, 1]
     *
     * @param nums
     * @param target
     * @return
     */
    static int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {

                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[]{};
    }

    /**
     * 2.两数相加
     * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
     *
     * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
     *
     * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
     *
     * 示例：
     *
     * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
     * 输出：7 -> 0 -> 8
     * 原因：342 + 465 = 807
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //返回的结果
        ListNode result = new ListNode(0);
        //中转链表
        ListNode node = result;
        int ys = 0 ; //余数
        ListNode l11 = l1,l22=l2;
        while (l11 != null || l22 != null){
            //l1各个节点的值
            int v1 = (l11==null?0:l11.val);
            //l2各个节点的值
            int v2 = (l22==null?0:l22.val);
            node.next = new ListNode((v1+v2+ys)%10);
            ys = (v1+v2+ys)/10;
            node=node.next;
            l11=(l11==null?null:l11.next);
            l22=(l22==null?null:l22.next);
        }
        if(ys>0){
            node.next = new ListNode(ys);
        }
        //因为第一次创建时的0不是想要的结果   所以返回 result.next
        return result.next;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    /**
     * 3. 无重复字符的最长子串
     * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
     *
     * 示例 1:
     *
     * 输入: "abcabcbb"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
     * 示例 2:
     *
     * 输入: "bbbbb"
     * 输出: 1
     * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
     * 示例 3:
     *
     * 输入: "pwwkew"
     * 输出: 3
     * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        //将字符串转成char数组 方便遍历
        char[] chars = s.toCharArray();
        //存储字符串
        StringBuilder sb = new StringBuilder();
        //result 结果  i中间变量
        int result=0,i;
        //遍历
        for (char c:chars) {
            //将遍历的结果拼接到StringBuilder中  如果出现重复 从重复位置截取保留 如果未出现重复 拼接
            if(sb.toString().contains(String.valueOf(c))){
                sb=new StringBuilder(sb.substring(sb.indexOf(String.valueOf(c))+1)+c);
            }else{
                sb.append(c);
            }
            //判断比较结果和中间变量的大小  结果取大的
            i=sb.length();
            if(i>result){
                result = i;
            }
        }
        return result;
    }

    /**
     * 4. 寻找两个有序数组的中位数
     *
     * 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
     *
     * 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
     *
     * 你可以假设 nums1 和 nums2 不会同时为空。
     *
     * 示例 1:
     *
     * nums1 = [1, 3]
     * nums2 = [2]
     *
     * 则中位数是 2.0
     * 示例 2:
     *
     * nums1 = [1, 2]
     * nums2 = [3, 4]
     *
     * 则中位数是 (2 + 3)/2 = 2.5
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //创建一个数组
        int[] a = new int[(nums1==null?0:nums1.length)+(nums2==null?0:nums2.length)];
        //把传来的两个数组存到一个完整数组中
        int index=0;
        assert nums1 != null;
        for (int i1:nums1) {
            a[index] = i1;
            index++;
        }
        assert nums2 != null;
        for (int i2:nums2) {
            a[index] = i2;
            index++;
        }
        //对新数组排序
        Arrays.sort(a);
        //如果数组长度是偶数 则中位数 是中间两个数的平均数 ，如果数组长度是奇数 则中位数是中间数
        if(a.length%2==0){
            return (double)(a[a.length/2-1]+a[a.length/2])/2;
        }else{
            return (double)a[a.length/2];
        }
    }

    /**
     * 5. 最长回文子串
     *给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
     *
     * 示例 1：
     *
     * 输入: "babad"
     * 输出: "bab"
     * 注意: "aba" 也是一个有效答案。
     * 示例 2：
     *
     * 输入: "cbbd"
     * 输出: "bb"
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {

        // #TODO 回文数

        return null;
    }



}